/*
 * Copyright (c) 2018-2023 北京华恒盛世科技有限公司
 * QUICKPOOL is licensed under Mulan PSL v2.
 * You can use this software according to the terms and conditions of the Mulan PSL v2.
 * You may obtain a copy of Mulan PSL v2 at:
 *     http://license.coscl.org.cn/MulanPSL2
 * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
 * EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
 * MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
 * See the Mulan PSL v2 for more details.
*/

#include <stdio.h>
#include "tree.h"

#ifndef FREEUP
#define FREEUP(p)   if (p != NULL) { \
                        free(p);     \
                        p = NULL;    \
                    }
#endif

/* create a tree */
struct tree *
tree_create(const char *name)
{
    struct tree *tr;
    int length;

    tr = (struct tree *)calloc(1, sizeof(struct tree));
    if (tr == NULL) {
        return NULL;
    }

    length = strlen(name) + 2;
    tr->name = (char *)calloc(length + 1, sizeof(char));
    if (tr->name == NULL) {
        FREEUP(tr);
        return NULL;
    }

    snprintf(tr->name, length, "/%s", name);

    tr->root = (struct treeNode *)calloc(1, sizeof(struct treeNode));
    if (tr->root == NULL) {
        FREEUP(tr);
        FREEUP(tr->name);
        return NULL;
    }

    tr->root->name = strdup("/");

    tr->root->parent = NULL;
    tr->node_table = gf_hash_make(11);
    tr->leaf_list = gf_list_make("leaf list");

    return tr;
}

/* destroy a tree */
void
tree_destroy(struct tree *tr)
{
    struct treeNode *node;

    while ((node = tree_remove_leaf(tr->root))) {
        if (node == tr->root) {
            break;
        }
        FREEUP(node->name);
        FREEUP(node);
    }

    FREEUP(tr->root->name);
    FREEUP(tr->root);
    FREEUP(tr->name);
    gf_hash_free(tr->node_table, NULL);
    gf_list_free(tr->leaf_list, NULL);
    FREEUP(tr);

    return;
}

/* insert the node as the left-most child of parent */
struct treeNode *
tree_insert_node(struct treeNode *parent, struct treeNode *node)
{
    if (NULL == parent) {
        return NULL;
    }

    if (NULL == parent->child) {

        parent->child = node;
        node->parent = parent;

        return node;
    }

    node->parent = parent;
    node->right = parent->child;
    node->left = parent->child->left;
    parent->child->left = node;
    parent->child = node;

    return node;
}

/* remove node from the tree */
struct treeNode *
tree_remove_node(struct treeNode *node)
{
    if (node->left) {
        node->left->right = node->right;
    }

    if (node->right) {
        node->right->left = node->left;
    }

    if (node->parent && node->parent->child == node) {
        node->parent->child = node->right;
    }

    return node;
}

/* traverse a tree */
int
tree_traverse(struct tree *tr, int (*func)(struct treeNode *, struct tree *))
{
    if (!tr->root) {
        return -1;
    }

    struct treeNode *node;
    node = tr->root;

    if (!node->child) {
        return (*func)(NULL, NULL);
    }

    LIST_T *childList;
    childList = gf_list_make("child node list");

    while (1) {

        while (NULL != node) {

            if (NULL != node->child) {

                LIST_PROXY_T *pxy;
                pxy = (LIST_PROXY_T *)calloc(1, sizeof(struct list_proxy));
                if (NULL == pxy) {
                    return -1;
                }

                pxy->subject = (void *)node;
                gf_list_insert(childList, childList->forw, (LIST_T *)pxy);
            }

            int ret;
            ret = (*func)(node, tr);

            if (0 > ret) {
                gf_list_free(childList, NULL);
                return ret;
            }

            node = node->right;
        }

        LIST_PROXY_T *pxy;
        pxy = (LIST_PROXY_T *)gf_list_pop(childList);
        if (NULL == pxy) {
            break;
        }

        node = (struct treeNode *)pxy->subject;
        FREEUP(pxy);
    }

    gf_list_free(childList, NULL);

    return (*func)(NULL, NULL);
}

/* return the next node, NULL if reach the end */
struct treeNode *
tree_next_node(struct treeNode *node)
{
    struct treeNode *parent;

    if (node == NULL)
        return NULL;

    if (node->child) {
        return node->child;
    }

    if (node->right) {
        return node->right;
    }

    parent = node->parent;
    while (parent) {
        if (parent->right) {
            return parent->right;
        }
        parent = parent->parent;
    }
    return NULL;
}

/* remove all the leaves under a node */
struct treeNode *
tree_remove_leaf(struct treeNode *node)
{
    if (node == NULL) {
        return NULL;
    }

    while (node) {
        if (node->child) {
            node = node->child;
        } else {
            break;
        }
    }

    tree_remove_node(node);

    return node;
}
